package leetcode.list;

import java.util.Arrays;

/**
 * Created by zxc on 2018/10/4.
 */
public class SortList {
    // Definition for singly-linked list.
    static class ListNode {
        int val;
        ListNode next;
        ListNode(int x) {
            val = x;
        }
    }

    /*简单的链表排序*/
    private static ListNode sortList(ListNode head) {
        if (head == null || head.next == null)
            return head;
        ListNode cur = head;
        int count = 0;
        //获取长度
        while (cur != null) {
            count++;
            cur = cur.next;
        }
        int[] arr = new int[count];
        int index = 0;
        cur = head;
        //值导入数组
        while (cur != null) {
            arr[index++] = cur.val;
            cur = cur.next;
        }
        //排序
        Arrays.sort(arr);

        cur = head;
        index = 0;
        //重新赋值
        while (cur != null) {
            cur.val = arr[index++];
            cur = cur.next;
        }
        return head;
    }

    public static void main(String[] args) {
        ListNode node1 = new ListNode(1);
        ListNode node2 = new ListNode(7);
        ListNode node3 = new ListNode(3);
        ListNode node4 = new ListNode(4);
        ListNode node5 = new ListNode(5);
        ListNode node6 = new ListNode(6);
        ListNode node7 = new ListNode(2);
        node1.next=node2;
        node2.next=node3;
        node3.next=node4;
        node4.next=node5;
        node5.next=node6;
        node6.next=node7;
        node7.next=null;
        ListNode head = node1;

        System.out.println("Before 排序：");
        while (head!=null){
            System.out.print(head.val+">");
            head = head.next;
        }
        System.out.println("end");

        /*排序*/
        ListNode newHead = sortList(node1);

        head = newHead;
        System.out.println("After 排序：");
        while (head!=null){
            System.out.print(head.val+">");
            head = head.next;
        }
        System.out.println("end");
    }
}
